package com.demo.algorithm;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * Created by hunter
 *
 * @Description 二叉树构造与遍历, 二叉排序树, 左边的子节点一定比根节点小，右边的子节点一定比根节点大
 */
public class BinTree {

    private static class TreeNode {
        private Integer data;
        private TreeNode leftChild;
        private TreeNode rightChild;

        public TreeNode(Integer data) {
            this.data = data;
        }

        TreeNode() {
        }

        @Override
        public String toString() {
            return String.valueOf(this.data);
        }
    }

    /**
     * 构建二叉树
     *
     * @param datas
     * @param node
     * @return
     */
    public static TreeNode buildTree(int[] datas, TreeNode node) {
        if (node == null) {
            node = new TreeNode();
        }

        for (int i = 0; i < datas.length; i++) {
            insertNode(datas[i], node);
        }

        return node;
    }

    /**
     * 插入节点
     *
     * @param data
     * @param node
     */
    public static void insertNode(Integer data, TreeNode node) {
        if (node.data == null || node.data.equals(data)) {
            node.data = data;
        } else if (node.data < data) {
            if (node.rightChild == null) {
                node.rightChild = new TreeNode();
            }
            insertNode(data, node.rightChild);
        } else if (node.data > data) {
            if (node.leftChild == null) {
                node.leftChild = new TreeNode();
            }
            insertNode(data, node.leftChild);
        }
    }

    /**
     * 先序遍历 根 -> 左 ->右
     *
     * @param rootNode
     */
    public static void preOrderTraverse(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        System.out.println(rootNode);
        preOrderTraverse(rootNode.leftChild);
        preOrderTraverse(rootNode.rightChild);
    }

    /**
     * 中序遍历 左 -> 根 ->  右
     *
     * @param rootNode
     */
    public static void inOrderTraverse(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        inOrderTraverse(rootNode.leftChild);
        System.out.println(rootNode);
        inOrderTraverse(rootNode.rightChild);
    }

    /**
     * 后序遍历 左 -> 右 -> 根
     *
     * @param rootNode
     */
    public static void postOrderTraverse(TreeNode rootNode) {
        if (rootNode == null) {
            return;
        }
        postOrderTraverse(rootNode.leftChild);
        postOrderTraverse(rootNode.rightChild);
        System.out.println(rootNode);
    }

    /**
     * 获取节点
     *
     * @param node
     * @param val
     * @return
     */
    public static TreeNode getNode(TreeNode node, int val, AtomicInteger queryDepth) {
        queryDepth.incrementAndGet();

        if (node == null || node.data == val) {
            return node;
        } else if (node.data < val) {
            return getNode(node.rightChild, val, queryDepth);
        } else {
            return getNode(node.leftChild, val, queryDepth);
        }
    }

    public static void main(String[] args) {
        int[] datas = {4, 3, 2, 0, 1, 6, 5, 7, 11, - 1};
        // int[] datas = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //这种数据情况下插入, 会形成一颗极端的二叉树, 影响查询深度
        TreeNode rootNode = buildTree(datas, null);

        System.out.println("--------- preOrderTraverse begin . -----------");
        preOrderTraverse(rootNode);
        System.out.println("--------- preOrderTraverse end . -----------");

        System.out.println("--------- inOrderTraverse begin . -----------");
        inOrderTraverse(rootNode);
        System.out.println("--------- inOrderTraverse end . -----------");

        System.out.println("--------- postOrderTraverse begin . -----------");
        postOrderTraverse(rootNode);
        System.out.println("--------- postOrderTraverse end . -----------");

        AtomicInteger queryDepth = new AtomicInteger(0);
        getNode(rootNode, datas[8], queryDepth);

        System.out.println("--------- query depth : " + queryDepth.intValue());
    }
}